package org.example.myleet.rosalind.lcsm;

import org.example.myleet.rosalind.utils.FastaReader;
import org.example.myleet.rosalind.utils.FastaSequence;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution {

    private static final char[] BASES = new char[]{'A', 'C', 'G', 'T'};

    public String findLongestCommonSubstring(List<FastaSequence> sequences) {
        Set<String> candidates = new HashSet<>();
        candidates.add("");
        Set<String> nextCandidates = new HashSet<>();
        boolean found;
        do {
            found = false;
            for (String candidate : candidates) {
                for (char base : BASES) {
                    //每次在候选的序列上依次延长A、C、G、T，并尝试是否存在于每一个序列中，如果全部都存在，就成为下一个候选序列
                    String motif = candidate + base;
                    if (isCommonSubstring(sequences, motif)) {
                        nextCandidates.add(motif);
                        found = true;
                    }
                }
            }
            if (found) {
                candidates = new HashSet<>(nextCandidates);
            }
            nextCandidates = new HashSet<>();
        } while (found);
        return candidates.iterator().next();
    }

    private boolean isCommonSubstring(List<FastaSequence> sequences, String motif) {
        for (FastaSequence sequence : sequences) {
            if (!sequence.getSequence().contains(motif)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String path = solution.getClass().getResource("").getPath() + "example.txt";
        System.out.println(solution.findLongestCommonSubstring(FastaReader.parseFastaFromFile(path)));
    }
}
